package com.mango.leet.code.week1.game284;

/**
 * 5227. K 次操作后最大化顶端元素
 */

/**
 * 给你一个下标从 0 开始的整数数组 nums ，它表示一个 栈 ，其中 nums[0] 是栈顶的元素。
 *
 * 每一次操作中，你可以执行以下操作 之一 ：
 *
 * 如果栈非空，那么 删除 栈顶端的元素。
 * 如果有超过 1 个或者多个被删除且不在栈中的元素，你可以从它们中选择任何一个，添加 回栈顶，这个元素成为新的栈顶元素。
 * 同时给你一个整数 k ，它表示你总共需要执行操作的次数。
 *
 * 请你返回 恰好 执行 k 次操作以后，栈顶元素的 最大值 。如果执行完 k 次操作以后，栈一定为空，请你返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [5,2,2,4,0,6], k = 4
 * 输出：5
 * 解释：
 * 4 次操作后，栈顶元素为 5 的方法之一为：
 * - 第 1 次操作：删除栈顶元素 5 ，栈变为 [2,2,4,0,6] 。
 * - 第 2 次操作：删除栈顶元素 2 ，栈变为 [2,4,0,6] 。
 * - 第 3 次操作：删除栈顶元素 2 ，栈变为 [4,0,6] 。
 * - 第 4 次操作：将 5 添加回栈顶，栈变为 [5,4,0,6] 。
 * 注意，这不是最后栈顶元素为 5 的唯一方式。但可以证明，4 次操作以后 5 是能得到的最大栈顶元素。
 * 示例 2：
 *
 * 输入：nums = [2], k = 1
 * 输出：-1
 * 解释：
 * 第 1 次操作中，我们唯一的选择是将栈顶元素弹出栈。
 * 由于 1 次操作后无法得到一个非空的栈，所以我们返回 -1 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 0 <= nums[i], k <= 109
 */
public class LC5227 {
    public static void main(String[] args) {
        int[] nums = {94,23,58,92,3,63,68,43,8,97,54,11,63,55,73,38,22,80,45,43,25,34,67,76,80,9,30,27,50,7,57,63,63,27,46,1,50,55,99,92,73,9,57,25,59,54,100,56,64,94,99};
        int k = 79;
        System.out.println(new Solution().maximumTop(nums,k));
    }
    static class Solution {
        public int maximumTop(int[] nums, int k) {
            int max = 0, n = nums.length;
            if(n == k % 2) return -1;
            // 找到k-1内或者n内的最大值
            for(int i = 0; i < Math.min(k - 1, n); i++){
                max = Math.max(max, nums[i]);
            }
            //
            return Math.max(max, k < n ? nums[k] : 0);
        }
    }
}
/**
 * 思路： 贪心取出前 k - 1个元素，第 k 次操作可以
 *
 * 将已经移除的最大的元素放回栈顶，或
 * 取出第 k 个元素，此时栈顶为第 k + 1 个元素
 * 分类讨论：
 *
 * 当 nums.length = 1 时，k 为奇数则会把唯一元素拿出，返回 -1
 * 当 kk > nums.length时，可以取出所有元素，做一些无效操作浪费次数，并保证最后将最大的元素放在栈顶，返回最大数 max
 * 当 kk < nums.length 时，取出前 k - 1 个元素，放回已取出的最大数或将第 k 个元素取出
 * 当 kk = nums.length 时，取出前 k - 1 个元素后，再取出一个会导致空栈，此时只能将最大的元素放回栈顶
 *
 */
